#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include "memory_dump.h"
#include "test_for_circular_linked_list.h"

int circular_list_init(circular_list_t** phead, unsigned int value)
{
    if(*phead == NULL)
    {
        *phead = (circular_list_t* )circular_linked_malloc(sizeof(circular_list_t));
        if(*phead == NULL)
        {
            return -1; //内存申请失败，返回 -1 
        }
        (*phead)->value = value;
        (*phead)->next = *phead;
        return 0; //头节点创建成功，返回 1 
    }
    return -1;
}

/**
 * @brief 在循环链表的头部插入节点
 * @param phead 指向头节点
 * @param value 节点数据
 * @return 0 成功， -1 失败
 */
int circular_head_insert(circular_list_t** phead, unsigned int value)
{
    if((phead != NULL) && (*phead != NULL))
    {
        circular_list_t* pnew = (circular_list_t* )circular_linked_malloc(sizeof(circular_list_t));
        circular_list_t* tail = *phead;
        if(pnew == NULL)
        {
            return -1;
        }
        pnew->value = value;
        while(tail->next != *phead) //查找尾结点
        {
            tail = tail->next;
        }
        pnew->next = *phead;
        *phead = pnew;
        tail->next = *phead; //指向新的头结点
        return 0;
    }
    return -1;
}

/**
 * @brief 在循环链表的尾部插入节点
 * @param phead 指向头节点
 * @param value 节点数据
 * @return 0 成功， -1 失败
 */
int circular_tail_insert(circular_list_t** phead, unsigned int value)
{
    if((phead != NULL) && (*phead != NULL))
    {
        circular_list_t* pnew = (circular_list_t* )circular_linked_malloc(sizeof(circular_list_t));
        circular_list_t* tail = *phead;
        if(pnew == NULL)
        {
            return -1;
        }
        pnew->value = value;
        while(tail->next != *phead) //查找尾结点
        {
            tail = tail->next;
        }
        tail->next = pnew;
        pnew->next = *phead;
        return 0;
    }
    return -1;
}

/**
 * @brief 从指定位置插入节点，所有节点的序号从 0 开始。
 * @param phead 指向头结点
 * @param pos_add 指定的插入位置，从 0 开始。
 * @param node_val 指定位置插入的节点的数据内容
 * @return 0 成功， -1 失败
 */
int circular_stick_node(circular_list_t** phead, unsigned int pos_add, unsigned int node_val)
{
    if((phead != NULL) && (*phead != NULL))
    {
        if(pos_add == 0)
        {
            circular_head_insert(phead, node_val);
        }
        else
        {
            circular_list_t* pnew = (circular_list_t* )circular_linked_malloc(sizeof(circular_list_t));
            circular_list_t* cur = *phead;
            if(pnew == NULL)
            {
                return -1;
            }
            pnew->value = node_val;
            while(--pos_add && (cur->next != *phead)) //如果 pos_add 超出链表节点总数，则尾插
            {
                cur = cur->next;
            }
            pnew->next = cur->next;
            cur->next = pnew;
        }
        return 0;
    }
    return -1;
}

/**
 * @brief 删除头节点
 * @param phead 传入头节点的地址
 * @return 0 成功， -1 失败
 */
int circular_head_delete(circular_list_t** phead)
{
    if(phead != NULL && *phead != NULL)
    {
        circular_list_t* cur = *phead;
        circular_list_t* tail = *phead;
        while(tail->next != *phead)
        {
            tail = tail->next;
        }
        *phead = (*phead)->next;
        tail->next = *phead;
        free(cur);
        *phead = NULL;
        return 0;
    }
    return -1;
}

/**
 * @brief 删除尾节点
 * @param phead 尾节点的地址
 * @return 0 成功， -1 失败
 */
int circular_tail_delete(circular_list_t** phead)
{
    if(phead != NULL && *phead != NULL)
    {
        circular_list_t *cur = *phead;
        circular_list_t *prev = NULL;
        while (cur->next != *phead) // 让指针停留在最后一个结点
        {
            prev = cur; // 记录cur前一个结点
            cur = cur->next;
        }
        free(cur);
        if(prev != NULL)
        {
            prev->next = *phead;
            cur = NULL;
        }
        else
        {
            *phead = NULL;
        }
        return 0;
    }
    return -1;
}

/**
 * @brief 删除指定位置的节点，所有节点的序号从 0 开始。
 * @param phead 头节点地址 
 * @param pos_del 指定的删除的位置，从 0 开始。
 * @return 0 成功， -1 失败
 */
int circular_delete_node(circular_list_t** phead, unsigned pos_del)
{
    if(phead != NULL && *phead != NULL)
    {
        circular_list_t *cur = *phead;
        circular_list_t *prev = NULL;
        if (pos_del == 0)
        {
            circular_head_delete(phead);
        }
        else
        {
            while (pos_del-- && (cur->next != *phead)) //如果 pos_del 超出链表节点总数，则尾删
            {
                prev = cur;
                cur = cur->next;
            }

            //仅有一节点时， pos_del 超出链表节点总数， 执行尾删操作时， prev 为空，不能对它进行操作
            free(cur);
            if(prev != NULL)
            {
                prev->next = cur->next;
                cur = NULL; // 释放内存后，指针设置为 NULL
            }
            else
            {
                *phead = NULL;
            }
        }
        return 0;
    }
    return -1;
}

/**
 * @brief 修改指定位置的节点的数据，所有节点的序号从 0 开始。
 * @param phead 头节点地址 
 * @param pos_del 指定的删除的位置，从 0 开始。
 * @return 0 成功， -1 失败
 */
int circular_revise_node(circular_list_t** phead, unsigned int pos, unsigned int node_val)
{
    if(phead != NULL && *phead != NULL)
    {
        circular_list_t *cur = *phead;
        while (pos-- && (cur->next != *phead))
        {
            cur = cur->next;
        }
        if(cur->next != *phead)
        {
            cur->value = node_val;
        }
    }
    return -1;
}

/**
 * @brief 摧毁链表，释放内存
 * @param phead 头节点地址 
 * @return 0 成功， -1 失败
 */
int circular_destroy_list(circular_list_t** phead)
{
    if(phead != NULL && *phead != NULL)
    {
        circular_list_t *cur = *phead; // 指向头节点
        circular_list_t *prev = NULL;  // 指向cur上一个节点
        while (cur->next != *phead)
        {
            prev = cur;      // 记录上一个节点地址
            cur = cur->next; // 移至下一个节点
            free(prev);      // 释放节点
        }
        if(cur->next == *phead)
        {
            free(cur);
            cur = NULL;
        }
        *phead = NULL;
        return 0;
    }
    return -1;
}

void circular_list_print(circular_list_t* list)
{
    if(list != NULL)
    {
        circular_list_t* cur = list;// 指向第一个节点
        printf(YELLOW "list:[");

        while(cur->next != list)
        {
            printf("%d,",cur->value);
            cur = cur->next;
        }
        //特别注意：退出时 cur 刚好指向最后一个节点
        printf("%d", cur->value);
        printf("]\n" NONE);
    }
    else
    {
        printf(YELLOW "list:[]\n" NONE);
    }
}

void test_for_circular_linked_list(void)
{
    circular_list_t* phead_cir = NULL;
    printf(YELLOW "test for circular linked list:\r\n" NONE);
    printf(YELLOW "STEP 1. create circular linked list.\r\n" NONE);
    if(0 == circular_list_init(&phead_cir, 7))
    {
        printf(YELLOW "list created!\r\n" NONE);
    }

    printf(YELLOW "STEP 2. test func circular_head_insert.\r\n" NONE);
    for(uint8_t i = 6; i > 0; i--)
    {
        circular_head_insert(&phead_cir, i);
    }
    circular_list_print(phead_cir);

    printf(YELLOW "STEP 3. test func circular_tail_insert.\r\n" NONE);
    for(uint8_t i = 8; i < 15; i++)
    {
        circular_tail_insert(&phead_cir, i);
    }
    circular_list_print(phead_cir);

    printf(YELLOW "STEP 4. test func circular_stick_node.\r\n" NONE);
    circular_stick_node(&phead_cir, 0, 512); //测试插入节点位置超出总节点数
    circular_stick_node(&phead_cir, 15, 1000); //测试插入节点位置超出总节点数
    circular_list_print(phead_cir);

    printf(YELLOW "STEP 5. test func circular_head_delete.\r\n" NONE);
    circular_list_t* phead_cir_test_head_del = NULL;
    circular_list_init(&phead_cir_test_head_del, 1024);
    circular_list_print(phead_cir_test_head_del);
    circular_head_delete(&phead_cir_test_head_del);
    circular_list_print(phead_cir_test_head_del);

    printf(YELLOW "STEP 6. test func circular_delete_node.\r\n" NONE);
    circular_list_t* phead_cir_test_del_node = NULL;
    circular_list_init(&phead_cir_test_del_node, 1023);
    circular_list_print(phead_cir_test_del_node);
    circular_delete_node(&phead_cir_test_del_node, 1);
    circular_list_print(phead_cir_test_del_node);

    printf(YELLOW "STEP 7. test func circular_tail_delete.\r\n" NONE);
    circular_tail_delete(&phead_cir);
    circular_list_print(phead_cir);

    printf(YELLOW "STEP 8. test func circular_tail_delete.\r\n" NONE); //测试仅一个节点的尾删
    circular_list_t* phead_cir_test_circular_tail_delete = NULL;
    circular_list_init(&phead_cir_test_circular_tail_delete, 511);
    circular_list_print(phead_cir_test_circular_tail_delete);
    circular_tail_delete(&phead_cir_test_circular_tail_delete);
    circular_list_print(phead_cir_test_circular_tail_delete);

    printf(YELLOW "STEP 9. test func circular_revise_node.\r\n" NONE); //测试仅一个节点的尾删
    circular_revise_node(&phead_cir, 0, 0);
    circular_revise_node(&phead_cir, 20, 0);
    circular_list_print(phead_cir);

    printf(YELLOW "STEP 9. test func circular_destroy_list.\r\n" NONE); //测试仅一个节点的尾删
    circular_destroy_list(&phead_cir);
    circular_list_print(phead_cir);


}
